// https://leetcode.cn/problems/find-all-anagrams-in-a-string/

// 算法思路总结：
// 1. 使用固定长度的滑动窗口（大小为p的长度）
// 2. 双哈希表统计字符频率和有效字符计数
// 3. 维护窗口内有效字符数量count
// 4. 当count等于p的长度时记录起始位置
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <string>

class Solution 
{
public:
    vector<int> findAnagrams(string s, string p) 
    {
        int n = s.size(), m = p.size();
        if (n < m) return {};

        int hash1[26] = {0}, hash2[26] = {0};
        vector<int> ret;

        for (const char& ch : p) 
            hash2[ch - 'a']++;

        for (int l = 0, r = 0, count = 0 ; r < n ; r++)
        {
            char in = s[r];
            hash1[in - 'a']++;
            if (hash1[in - 'a'] <= hash2[in - 'a'])
                count++;    
            while (r - l + 1 > m)
            {
                char out = s[l];
                l++;
                hash1[out - 'a']--;
                if (hash1[out - 'a'] < hash2[out - 'a'])
                    count--;
            }
            if (count == m) 
                ret.push_back(l);
        }
        return ret;
    }
};

int main()
{
    string s1 = "cbaebabacd", s2 = "abab";
    string p1 = "abc", p2 = "ab";
    Solution sol;

    auto v1 = sol.findAnagrams(s1, p1);
    auto v2 = sol.findAnagrams(s2, p2);

    for (const int& num : v1)
        cout << num << " ";
    cout << endl;

    for (const int& num : v2)
        cout << num << " ";
    cout << endl;

    return 0;
}